#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct PAM
{
    int sz, tot, last;
    int ch[300005][26], len[300005], fail[300005];
    int s[300005];

    PAM()
    {
        sz = -1;
        s[0] = -1;
        node(0);
        node(-1);
        fail[0] = 1;
    }

    int node(int l)
    {
        sz++;
        len[sz] = l;
        return sz;
    }

    int getfail(int x)
    {
        while (s[tot - len[x] - 1] != s[tot])
            x = fail[x];
        return x;
    }

    void insert(int c)
    {
        s[++tot] = c;
        int now = getfail(last);
        if (!ch[now][c])
        {
            int x = node(len[now] + 2);
            fail[x] = ch[getfail(fail[now])][c];
            ch[now][c] = x;
        }
        last = ch[now][c];
    }
};